﻿#define _CRT_SECURE_NO_WARNINGS  1
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;


//704.⼆分查找
class Solution1 {
public:
    int search(vector<int>& nums, int target)
    {
        int n = nums.size();
        int left = 0, right = n - 1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (target > nums[mid])
            {
                left = mid + 1;
            }
            else if (target < nums[mid])
            {
                right = mid - 1;
            }
            else
            {
                return mid;
            }
        }

        return -1;

    }
};

//Leetcode34.在排序数组中查找元素的第⼀个和最后⼀个位置
class Solution2{
public:
    vector<int> searchRange(vector<int>& nums, int target)   // 暴力查找O(n)
    {
        int n = nums.size();
        int left = 0, right = n - 1;
        vector<int> ret{ -1,-1 };
        int i = 0;
        while (i < n && nums[i] != target)
        {
            i++;
        }

        int j = i;
        while (j < n && nums[j] == target)
        {
            j++;
        }

        if (i < n)
        {
            ret[0] = i;
            ret[1] = j - 1;
        }

        return ret;
    }
};

class Solution2_1 {
public:
    vector<int> searchRange(vector<int>& nums, int target)   // 二分
    {
        int n = nums.size();
        int left = 0, right = n - 1;
        
};


// 35.搜索插⼊位置
 class Solution3 {
    public:
        int searchInsert(vector<int>& nums, int target)
        {
            int n = nums.size();
            int left = 0, right = n - 1;
            int mid = (n - 1) / 2;
            if (target < nums[0]) return 0;
            else if (target > nums[n - 1]) return n;
            while (left <= right)
            {
                mid = left + (right - left) / 2;
                if (target < nums[mid])
                {
                    right = mid - 1;
                }
                else if (target > nums[mid])
                {
                    left = mid + 1;
                }
                else
                {
                    return mid;
                }
            }

            if (nums[mid] > target)
            {
                return mid;
            }
            else if (nums[mid] < target)
            {
                return mid + 1;
            }
            else return -1;
        }
    };


//69.x的平⽅根
class Solution4 {
    public:
        int mySqrt(int x)
        {
            int left = 1; int right = x;
            long long int mid;
            while (left <= right)
            {
                mid = left + (right - left) / 2;
                if (mid * mid > x)
                {
                    right = mid - 1;
                }
                else if (mid * mid < x)
                {
                    left = mid + 1;
                }
                else return mid;
            }
            if (left > right)
                return right;
            else
                return left;

        }
    };


//852.⼭脉数组的峰顶索引
class Solution5 {
    public:
        int peakIndexInMountainArray(vector<int>& arr)
        {
            int n = arr.size();
            int left = 0, right = n - 1;
            while (left < right)
            {
                if (arr[left] < arr[right])
                {
                    left++;
                }
                else if (arr[left] > arr[right])
                {
                    right--;
                }
                else left++, right--;
            }

            return left;
        }
    };


//162.寻找峰值
class Solution6 {
    public:
        int findPeakElement(vector<int>& nums)
        {
            int left = 0, right = left + 2;
            if (nums.size() == 2)
            {
                return nums[0] > nums[1] ? 0 : 1;
            }
            if (nums.size() == 1)
            {
                return 0;
            }

            while (right < nums.size())
            {
                if (nums[left] < nums[left + 1] && nums[right] < nums[left + 1])
                {
                    return left + 1;
                }
                else
                {
                    left++, right++;
                }
            }

            return nums[0] > nums[nums.size() - 1] ? 0 : nums.size() - 1;
        }
    };

int main()
{

}